Discrete Mathematics: Foundations of Tree Structures

In the realm of graph theory, a Tree is the architectural personification of order. Unlike chaotic networks where multiple paths might lead to the same destination, a tree provides a singular, unique journey between any two points. This structural constraint is not a limitation, but the very foundation of hierarchical systems—from the ancestral lineages of Greek gods to the directory structures of modern operating systems.

1. The Anatomy of a Tree

Before hierarchy exists, we have the Free Tree. Its definition is elegant in its simplicity:

Definition 9.1.1

A (free) tree $T$ is a simple graph where for any two vertices $v$ and $w$, there exists a unique simple path from $v$ to $w$. This implies the graph is both connected and acyclic (no cycles).

When we designate a specific vertex as the "origin," we create a Rooted Tree. This transformation introduces a spatial orientation, where relationships are defined by their distance and direction from the root.

The Hierarchical Lexicon

In a tree with root $v_0$, consider a simple path $(v_0, v_1, \dots, v_n)$:

Parent: The vertex $v_{n-1}$ is the parent of $v_n$.
Child: $v_n$ is a child of $v_{n-1}$.
Siblings: Vertices that share the same parent.
Ancestors: All vertices on the path from the root to $v_n$ (excluding $v_n$ itself in some contexts).
Descendants: All vertices that have $v$ as an ancestor.

Structural Metrics

Level: The length of the unique path from the root to a vertex. The root itself sits at Level 0.
Height: The maximum level number present in the tree.
Leaf (Terminal Vertex): A vertex with no children—the end of a branch.
Internal (Branch) Vertex: A vertex that has at least one child.

🎯 Core Concept: Subtrees

A subtree is a subset of a tree consisting of a vertex and all its descendants. In a file system, this is a folder and every file/subfolder inside it. In Figure 9.2.1, the lineage of Kronos (Zeus, Poseidon, Hades, Ares) is a subtree of Uranus.

2. Real-World Implementations

Trees are not just mathematical abstractions. They are the backbone of organization:

Computer File Systems: The 'C:' drive is the root; folders are internal vertices; files are leaves.
Administrative Charts: The CEO is the root; managers are internal nodes; individual contributors are leaves.
Decision Frameworks: Solving puzzles like Instant Insanity or analyzing n-cube planarity often involves navigating tree-like state spaces.

QUESTION 1

In the context of the Greek Mythology Family Tree (Figure 9.2.1), if Kronos's children are Zeus, Poseidon, Hades, and Ares, who are the siblings of Ares?

Zeus, Poseidon, and Hades

Uranus and Kronos

Only Zeus

Kronos and Aphrodite

QUESTION 2

What is the level of the root in any rooted tree?

Level 0

Level 1

Level n-1

It depends on the height

QUESTION 3

How is a 'Leaf' (Terminal Vertex) distinguished from an 'Internal' (Branch) Vertex?

A leaf has no children, while an internal vertex has at least one child.

A leaf is always at Level 0.

Internal vertices are always at the maximum height.

Leaves must have siblings.

QUESTION 4

Explain why, if we allow cycles of length 0 (a path from a vertex to itself with no edges), a single vertex graph is not acyclic.

Because the single vertex would technically contain a cycle of length 0.

Because a tree must have at least two vertices.

Because a single vertex is not connected.

Because it would violate the n-1 edges rule.

QUESTION 5

Based on the reading context, who is the parent of Poseidon in the Greek Mythology tree?

Kronos

Uranus

Zeus

Aphrodite

Lesson 9 Challenge: Structural & Optimization Logic

Applying Tree Theory to Combinatorial Problems

Trees provide the backbone for solving optimization and search problems. Use the principles of greedy algorithms, backtracking, and structural properties to solve the following challenges.

In a graph where vertices represent cities and weighted edges represent construction costs (a-g, weights 5-30), how do we find the least-expensive road system?

Solution: Construct a Minimal Spanning Tree (MST) using Prim's Algorithm. Start with any city, then repeatedly add the lowest-weight edge that connects a city in our set to one outside the set, ensuring no cycles are formed until all cities are connected.

Show that there is no solution to the two-queens or the three-queens problem.

Solution: For the 2-queens problem (2x2 grid): If you place a queen at (1,1), it attacks the rest of the row, column, and diagonal, leaving no safe spot for the second queen. For the 3-queens problem (3x3 grid): Placing a queen in any cell attacks enough of the grid that the remaining two queens cannot be placed without attacking each other or the first queen. For instance, placing the first at (1,1) attacks (1,2), (1,3), (2,1), (3,1), and (2,2), (3,3). No configuration of 3 queens avoids all conflicts.

Show that if denominations are 1, 8, and 10 cents, a greedy algorithm does not always produce the minimum number of stamps for a given amount.

Solution: Suppose we need 16 cents of postage. Greedy approach: Takes the largest possible (10), then 1, 1, 1, 1, 1, 1. Total = 7 stamps. Optimal approach: Takes two 8-cent stamps. Total = 2 stamps. Thus, the greedy choice of 'largest first' fails to find the global minimum.

Give an algorithm to construct a binary search tree.

Algorithm: 1. Start with the first element as the root. 2. For each subsequent element $x$: a. Compare $x$ with the current node $v$. b. If $x < v$, move to the left child. c. If $x > v$, move to the right child. d. If the target child is null, insert $x$ there; otherwise, repeat step 2 starting from that child.

What does it mean for two free trees to be isomorphic?

Solution: Two free trees $T_1$ and $T_2$ are isomorphic if there is a bijection $f: V(T_1) \to V(T_2)$ that preserves adjacency. That is, for any vertices $v, w$ in $T_1$, an edge exists between $v$ and $w$ if and only if an edge exists between $f(v)$ and $f(w)$ in $T_2$. Structural properties like degrees and path lengths are identical.